package codingforgreat.class07;

public class Class01_MaxAndValue {
    public static int maxAndValue1(int[] arr) {
        int N = arr.length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                max = Math.max(arr[i] & arr[j],max);
            }
        }
        return max;
    }
    public static int maxAndValue2(int[] arr){
        int N = arr.length;
        int M = arr.length;
        int ans = 0;
        for (int bit = 30; bit >= 0 ; bit--) {
            int temp = M;
            int i = 0;
            while(i < M){
                if ((arr[i] & (1 << bit)) == 0) {
                    swap(arr, i, --M);
                } else {
                    i++;
                }
            }
            if(M == 2){
                return arr[0] & arr[1];
            }
            if(M < 2 ){
                M = temp;
            }else if(M > 2) {
                ans |= (1 << bit);
            }
        }
        return ans;
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int[] randomArray(int size, int range) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (Math.random() * range) + 1;
        }
        return arr;
    }

    public static void main(String[] args) {
        int maxSize = 50;
        int range = 30;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int size = (int) (Math.random() * maxSize) + 2;
            int[] arr = randomArray(size, range);
            int ans1 = maxAndValue1(arr);
            int ans2 = maxAndValue2(arr);
            if (ans1 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束");

    }

}
